package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

@XClassic
public class LC104_MaximumDepthOfBinaryTree {
    public static void main(String[] args) {

    }

    @XOptimal
    static
    class Solution {
        public int maxDepth(TreeNode root) {
            return root == null ?
                    0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }

    static
    class Solution1 {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
    
    static
    class Solution2 {
        private int max = 0;

        public int maxDepth(TreeNode root) {
            doMaxDepth(root, 0);
            return max;
        }

        private void doMaxDepth(TreeNode root, int count) {
            if (root == null) {
                return;
            }
            count++;
            max = Math.max(max, count);
            doMaxDepth(root.left, count);
            doMaxDepth(root.right, count);
        }
    }
}
